package com.huawei.od;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

/**
 * 496. 下一个更大元素 I
 * 运用单调栈
 */
public class TestTwo {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2})));
    }

    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> tempStack = new Stack<>();
        int[] result = new int[nums1.length];
        // 数组初始化填充
        Arrays.fill(result, -1);
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            hashMap.put(nums1[i], i);
        }
        tempStack.add(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] > nums2[tempStack.peek()]) {
                while (!tempStack.isEmpty() && nums2[tempStack.peek()] < nums2[i]) {
                    if (hashMap.containsKey(nums2[tempStack.peek()])) {
                        Integer index = hashMap.get(nums2[tempStack.peek()]);
                        result[index] = nums2[i];
                    }
                    tempStack.pop();
                }
            }
            tempStack.add(i);
        }
        return result;
    }
}
